/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-11-15
 * Time: 22:12
 */


// 416. 分割等和子集

class Solution2 {
    //在原有动态规划思想上的，空间优化一下
    public boolean canPartition(int[] nums) {
        //分割等和子集
        //和之前做的0-1背包问题很像，我觉得我们需要做的也就是在这个nums数组中，找到能凑成所有元素和的 一半的组合就行了（每个元素只使用一次）
        //我觉得如果nums这个数组中的所有元素的和的 一半是一个小数，我觉得那应该就无法分割，直接返回false即可
        int len=nums.length;
        int sum=0;
        for(int i=0;i<len;i++){
            sum+=nums[i];
        }
        int rder=sum%2;//余数，如果余数为0，就代表整除了，如果余数为1，就代表无法整除2，就直接返回false
        if(rder==1){
            return false;
        }

        int midSum=sum/2;//数组所有元素的和的  一半

        //在数组nums中找，是否能够凑出和为midSum的组合
        boolean[] dp=new boolean[midSum+1];
        //相当于必须把背包装满的0-1背包问题
        //初始化
        //约定dp的值为false，代表没有找不到的情况
        dp[0]=true;//boolean类型的初始化默认会是false，所以这里需要特殊的把【0，0】位置初始化成true才对，这个点需要注意, 第一行的其他位置已经是默认的false了，不动就可以


        for(int i=1;i<=len;i++){
            for(int j=midSum;j>=1;j--){
                //空间优化版本要注意填表顺序的改变：从右往左(主要是对j的方向的改变)

                //i相当于在nums数组的【0，i-1】下标中寻找是否有和等于j的组合
                //j代表我们的相当于是midSum

                //不装入背包
                boolean a=dp[j];
                //装入背包
                boolean b=false;
                if((j-nums[i-1])>=0 ){
                    b=dp[j-nums[i-1]];
                }

                dp[j]=(a||b);
            }
        }

        return dp[midSum];
    }

}
